/**
 * 最大堆（一种完全二叉树）
 *
 * @author lzhphantom
 * @date 创建于 9:20 2020/8/6
 * @modified
 */
public class Heap {
    /**
     * 堆的大小
     */
    int size;
    /**
     * 模拟树<br/>
     * 节点下标为i，父节点为(i-1)/2<br/>
     * 节点下标为i，左边子节点为2i+1,右边子节点为2i+2
     */
    int[] array;

    public Heap(int[] array) {
        this.array = new int[array.length];
    }

    public void push(int x) {
        // 堆没有元素时，使元素成为顶点后退出
        if (size == 0) {
            array[0] = x;
            size++;
            return;
        }
        int i = size;
        // 如果下标存在
        // 将小的值 x 一直上浮
        while (i > 0) {
            int parent = (i-1) / 2;
            // 如果插入的值小于等于父亲节点，那么可以直接退出循环
            if (x <= array[parent]) {
                break;
            }
            // 否则将父亲节点与该节点互换，然后向上翻转，将该元素往上推
            array[i] = array[parent];
            i = parent;
        }
        // 将该值 x 放在不会再翻转的位置
        array[i] = x;
        // 堆数量加一
        size++;
    }

    public int pop() {
        // 没有元素，返回-1
        if (size == 0) {
            return -1;
        }
        // 根节点
        int ret = array[0];

        // 因为根节点要被删除了，将最后一个节点放到根节点的位置上
        size--;
        int x = array[size];
        array[size] = ret;

        int i = 0;
        while (true) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            // 左子节点下标超出了，表示没有左子树，那么右子树也没有，直接返回
            if (left >= size) {
                break;
            }
            // 有右子树，拿到两个子节点中较大节点的下标
            if (right < size && array[right] > array[left]) {
                left = right;
            }
            // 父节点的值都大于或等于两个子节点较大的那个，不需要向下继续翻转了，返回
            if (x >= array[left]) {
                break;
            }
            // 将较大的儿子与父亲交换，维持这个最大堆的特征
            array[i] = array[left];
            i = left;
        }
        array[i] = x;
        return ret;
    }
}
